// https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */


 func lcaDeepestLeaves(root *TreeNode) *TreeNode {
	var max_depth = -1
	var ans *TreeNode
	var trave func (*TreeNode, int) int
	trave = func (root *TreeNode, d int) int{
		if root == nil {
			max_depth = max(max_depth, d)
			return d
		}
		left_max_depth := trave(root.Left, d + 1)
		right_max_depth := trave(root.Right, d + 1)
		if left_max_depth == right_max_depth && left_max_depth == max_depth {
			ans = root
		}
		return max(left_max_depth, right_max_depth)
	 }
    trave(root, 0)
	return ans
 }